#ifndef __HRV64GENERATOR_H__
#define __HRV64GENERATOR_H__

#include "HIRCode.h"
//#include <map>

// stack location
typedef uint32_t stloc_t;

struct bb_stack {
	// stack pointer address to hold necessary local temps
	stloc_t sp;
	// the MAX number of arguments to pass on stack
	uint32_t nargs_on_stack;
};

// Register descriptor: specifying which temp's NEWEST value is held
//typedef HIRTempno RegDesc;
/*
 * A GPR may hold not only a temporary but also address of
 * an external symbol. When it holds the latter, `xsymidx`
 * is the index of the symbol in `_xsyms`.
 */
struct RegDesc {
	union {
		HIRTempno tempno;
		uint32_t xsymidx;
	};
	/*
	 * `RESERVED` means that this register has special use,
	 * so it cannot be allocated for temporaries. For example:
	 * ZERO, SP, RA, GP, TP.
	 */
	enum {RESERVED, FREE, TEMP, XSYM} status;
	/*
	 * The reg has been allocated to some temps
	 * using graph coloring registor allocation.
	 */
	bool flag_allocated;
};

// Hypothetical stack frame base address
#define FRAME_BASE 0xf0000000u
// Invalid stack location
#define INVALID_STLOC 0u

// Address descriptor of temp: specifying where the NEWEST value can be found
struct TempDesc {
	// In a GPR/FPR. `ZERO` means invalid.
	RV64GFR reg;
	/*
	 * Stored in stack: `stloc` is the relative location.
	 * `0U` is invalid location.
	 */
	stloc_t stloc;
	// Static value: for the pointers defined by `ALLOCA`
	stloc_t stval;
	/*
	 * Specifying which values above are invalid.
	 * NOTE: if `status` doesn't have `STACK`, `stloc` might also be valid.
	 * In this situation, the temp has been allocated space on the stack
	 * but its newest value is not on stack (in a GPR/FPR).
	 */
	int32_t status;
	enum TempStatus {UNKNOWN = 0, REG = 1, STACK = 2,
		STATIC = 4, ALLOCATED = 8};
	TempDesc() {
		reg = RV64GFR::ZERO; stloc = stval = INVALID_STLOC; status = UNKNOWN;
	}
};

struct RV64Inst {
	// instruction operation
	RV64Oper oper;
	// operand size (byte, half word, word, double word...)
	RV64Opsz size;
	// source reg 1
	union {
		RV64GFR src1;
		RV64GFR base;
		RV64GFR fsrc1;
	};
	// source reg 2
	union {
		RV64GFR src2;
		RV64GFR fsrc2;
	};
	// destination reg
	union {
		RV64GFR dest;
		RV64GFR fdest;
	};
	// immediate
	union {
		int64_t imm12;		// for `addi`, ..., `slti`
		int64_t off12;		// for memory access
		uint64_t xsymidx;	// for `la`, `ld`(symbol)
		int64_t imm64;		// for `li`
		uint64_t labelno;	// for label and `j`, `b`cond
		uint64_t functidx;	// for `call`, the index in `HIRCode`!
	};
	std::string *cominfo;	// comment info
	RV64Inst(RV64Oper op = RV64Oper::NOP, RV64Opsz sz = RV64Opsz::D,
		std::string *com = nullptr) {
		oper = op; size = sz;
		src1 = src2 = dest = RV64GFR::ZERO;
		imm64 = 0l;
		cominfo = com;
	}
};

// Whether an imm can be represented in a 12-bit signed imm
static inline bool is_imm12(int64_t imm)
{
#define IMM12_MAX int64_t(~(~0l << 11))
#define IMM12_MIN int64_t(~0l << 11)
#define IMM12_ABS_MAX uint32_t(~(~0u << 11))
	return (imm >= IMM12_MIN && imm <= IMM12_MAX);
}

struct RV64XSymbol {
	// symbol name
	std::string id;
	// Storage type
	enum {DATA, RODATA, BSS} sttype;
	uint32_t size;	// size in byte
	uint32_t align;	// log of 2: the alignment in byte is `1<<align`
#define RV64_ALIGN_MAX 6u	// 64 B max
	const void *data;
};

// This union is used to represent 4 regs in a 64-bit integer
union RV64regs_t {
	uint64_t regs;
	uint16_t reg[sizeof(uint64_t) / sizeof(uint16_t)];
};

// Get corresponding `RV64Opsz` from `HIRBtype` or `DEFAULT` if unknown
static inline RV64Opsz hirbtype2rv64opsz(HIRBtype btype)
{
	RV64Opsz sz;
	switch (btype)
	{
	case HIRBtype::DOUBLE: case HIRBtype::POINTER:
		sz = RV64Opsz::D; break;
	case HIRBtype::FLOAT:
		sz = RV64Opsz::S; break;
	case HIRBtype::I32:
	// If `int` is implemented by 64-bit, change it to `D`
		sz = RV64Opsz::W; break;
	case HIRBtype::I8:
		sz = RV64Opsz::B; break;
	default:
		sz = RV64Opsz::DEFAULT; break;
	}
	return sz;
}

/*
 * Denote by which an argument is passed
 * during a function call
 */
struct RV64ArgPassing {
	union {
		// GPR/FPR
		RV64GFR reg;
		// stack offset (relative to `$sp`) (byte)
		uint32_t stoff;
	};
	bool use_reg;
};


// HXD1D Interference graph vertex
struct HIGVertex {
	// The vertex is valid, rather than simplified or coalesced.
	bool valid;
	// Floating-point temp or integer?
	bool is_float;
	// The vertex has been allocated a register
	bool allocated;
	// The register that it is allocated
	RV64GFR reg;
	/*
	 * When two vertexes are coalesced, one vertex
	 * may have more than one temporaries.
	 * So `std::set` is needed.
	 * NOTE: in base class `HInterferenceGraph`, it must
	 * contains ONLY ONE temp as vertexes in it should NOT be coalesced!!!
	 */
	std::set<HIRTempno> temps;
	// Indexes of all its adjacencies
	std::set<size_t> adjlist;
	HIGVertex(HIRTempno t, bool is_float, bool valid = true,
		bool allocated = false, RV64GFR reg = RV64GFR::ZERO)
	{
		this->valid = valid;
		this->is_float = is_float;
		this->allocated = allocated;
		this->reg = reg;
		this->temps.insert(t);
	}
	size_t degree_all(void) const { return adjlist.size(); }
};

// Copy (or, move) edge (NOT interference edge) in the graph
struct HIGCopy {
	// The two vertexes of the copy edge
	size_t igv1, igv2;
	// Indexes of corresponding copy (move) instructions
	std::set<uint32_t> insts;
	/*
	 * The status of the copy, only `NORMAL` edges may be coalesced.
	 * `COALESCED`: this two vertexes have been coalesced;
	 * `FROZEN`: this two vertexes have been frozen;
	 * `CONSTRAINED`: this two vertexes are interfering;
	 * `REDUNDANT`: when three edges forms a triangle and one of them
	 * 		coalesced, another would become `REDUNDANT`.
	 */
	enum CopyStatus {NORMAL, COALESCED, FROZEN, CONSTRAINED,
		REDUNDANT} status;
	HIGCopy(size_t igv1, size_t igv2, uint32_t inst, CopyStatus status = NORMAL)
	{
		this->igv1 = igv1; this->igv2 = igv2;
		insts.insert(inst);
		this->status = status;
	}
};

/*
 * Base class for HXD1D interference graph that is
 * used to store original information and does NOT
 * support simplifying and coloring operations.
 */
class HInterferenceGraph {
protected:
	// Vertexes of the graph
	std::vector<HIGVertex> vertexes_;
	// Copy (move) edges
	std::vector<HIGCopy> copies_;
public:
	// Error information
	static const char * const Error;
	// Access private members
	const std::vector<HIGVertex> & vertexes(void) const { return vertexes_; }
	const std::vector<HIGCopy> & copies(void) const { return copies_; }

	// Constructors
	HInterferenceGraph() = default;
	HInterferenceGraph(const std::vector<HIGVertex> & vertexes,
		const std::vector<HIGCopy> & copies) {
		// For constructing `HWorkingIGraph`...
		vertexes_ = vertexes; copies_ = copies;
	};
	// Deleted assignment operator
	HInterferenceGraph & operator=(const HInterferenceGraph &) = delete;

	// Basic functions
	size_t degree_of(size_t vtxi, bool all = false) const;
	virtual const void build_from_hirfunct(const HIRFunct & irfunct);
	virtual size_t add_vertex(HIRTempno t, bool is_float, bool preallocated = false,
		RV64GFR reg = RV64GFR::ZERO);
	virtual uint64_t add_edge(HIRTempno u, HIRTempno v);
	virtual size_t add_copy(HIRTempno u, HIRTempno v, uint32_t inst_idx);
	virtual size_t search_vertex(HIRTempno t) const;
	size_t search_copy(size_t igv1, size_t igv2 = SIZE_MAX,
		bool any_status = false) const;
	virtual void print(std::ostream & os, char line_prefix = '#') const;
	
	// Supporting graph coloring
	virtual HIRTempno spill_actual(const std::set<HIRTempno> &already_spilled,
		const std::vector<HIRTemp> &temps) const;

	// Destructor
	virtual ~HInterferenceGraph() { };
};

/*
 * Working interference graph for creating a copy of the original graph.
 * It has some functions to support coloring and also deletes some functions.
 */
class HWorkingIGraph : public HInterferenceGraph {
public:
	// Number of available GPRs/FPRs
	static const size_t NAGPR = 24ul;
	static const size_t NAFPR = 29ul;
	// Available GPRs/FPRs
	static const RV64GFR Available_GPR[NAGPR];
	static const RV64GFR Available_FPR[NAFPR];
private:
	std::vector<size_t> simplified_stack_;
public:
	// Constructor from original graph
	//HWorkingIGraph(const HInterferenceGraph & Oig,
	//	const std::set<HIRTempno> &spilled);
	void build_from_oig(const HInterferenceGraph & Oig,
		const std::set<HIRTempno> &spilled);

	// Rewritten functions
	virtual size_t search_vertex(HIRTempno t) const;
	
	// Coloring functions, returning non-zero value if changed.
	uint64_t simplify(void);
	uint64_t coalesce(void);
	uint64_t freeze(void);
	uint64_t spill_potential(void);
	uint64_t select(void);

	// For debug
	virtual void print(std::ostream & os, char line_prefix = '#') const;
};

class RV64Funct {
private:
	// Which IR function is this from
	const HIRCode *ircode_;
	size_t hirfidx_;
	// name
	std::string id_;
	// RV64 code
	std::vector<RV64Inst> code_;
	// Temp descriptors
	std::vector<TempDesc> tdescs_;
	// Reg descriptors
	RegDesc rdescs_[unsigned(RV64GFR::NGFR)];
	// The hypothetical stack frame base address
	stloc_t frame_base_;
	/*
	 * `_static_top` ~ `_frame_base` is the area
	 * to store `$ra`, local variables (by `ALLOCA`),
	 * non-local temps, and callee-saved GPRs and FPRs.
	 * NOTE: "static" means independence between BBs.
	 */
	stloc_t static_top_;
	/*
	 * `_static_top` ~ `_bb_stacks[#bb].sp` is the space
	 * used for local temps of every BB.
	 */
	std::vector<bb_stack> bb_stacks_;
	/*
	 * `_common_sp` is the address as which `$sp` should be
	 * set at the beginning (prologue) of the function.
	 * It equals the ALIGNED lowest `_bb_sp`.
	 */
	stloc_t common_sp_;
	/*
	 * Map saved regs to their saved stack location.
	 * Use `INVALID_STLOC` to represent that this reg
	 * should be saved but has not been allocated.
	 */
	std::map<RV64GFR, stloc_t> saved_regs_;
	/*
	 * Save the indexes of all stack access (load/store/addi) instructions.
	 * In code generation, instruction accessing the stack has FAKE
	 * (hypothetical) address. So the actual offset need to be filled
	 * in the end, when the stack size thus value of `$sp` is determined.
	 * NOTE: new instruction may be inserted if the offset is too large
	 * for the 12-bit signed offset. In this case, indexes should be updated!
	 */
	std::vector<uint32_t> stack_access_list_;
	// The label of the function epilogue
	HIRLabel epilogue_;
	// Original interference graph
	HInterferenceGraph intgraph_;
	// Working interference graph
	HWorkingIGraph wintgraph_;
public:
	// Construct an object from `ircode`
	RV64Funct(size_t hirfidx, const HIRCode &ircode, bool is_builtin = false);
	// Get member...
	const std::string & id(void) const { return id_; }
	const stloc_t frame_base(void) const { return frame_base_; }
	const stloc_t static_top(void) const { return static_top_; }
	const stloc_t common_sp(void) const { return common_sp_; }
	const std::vector<bb_stack> & bb_stacks(void) const { return bb_stacks_; }
	const std::vector<RV64Inst> code(void) const { return code_; }
	const HIRLabel epilogue(void) const { return epilogue_; }
	const HInterferenceGraph & intgraph(void) const { return intgraph_; }
	const HWorkingIGraph & workingintgraph(void) const { return wintgraph_; }
	// Initialization functions...
	void init_argumens(size_t nargs);
	void reset_desc(uint32_t bbidx = INVALID_BB_IDX);
	stloc_t allocate_unit(size_t size, size_t alignment = 8ul,
		uint32_t bbidx = INVALID_BB_IDX);
	void allocate_static(void);
	// Register allocation...
	void build_interference_graph(void);
	uint64_t reg_alloc(void);
	std::set<HIRTempno> get_temps_sharing_reg(HIRTempno t) const;
	// Generate RV64 code...
	void load_temp_to_reg(HIRTempno temp, RV64GFR reg);
	void temp_writeback(HIRTempno t, uint32_t bbidx);
	uint64_t get_regs(uint32_t inst_idx, uint32_t bb_idx, HIRTempno dest,
		const std::vector<HIRTempno>& srcs, const bool *fp_src = nullptr,
		bool allow_dest_reuse = true);
	HIRTempno get_regs(RV64GFR reg, uint32_t bbidx);
	void save_temps_to_stack(uint32_t bbidx);
	void generate_bb_code(uint32_t bbidx);
	void generate_function_call(uint32_t bbidx, size_t inst_idx);
	void stack_access_backpatch(void);
	void generate_prologue_and_epilogue(void);
	void generate_code(void);

	// Append RV64 instructions... (Return: index or reserved.)
	uint64_t append_label(uint64_t labelno);
	uint64_t append_arlo(RV64Oper op, RV64GFR src1, RV64GFR src2, RV64GFR dest,
		RV64Opsz sz = RV64Opsz::DEFAULT, std::string *cominfo = nullptr);
	uint64_t append_arloi(RV64Oper op, RV64GFR src1, int64_t imm12, RV64GFR dest,
		RV64Opsz sz = RV64Opsz::DEFAULT, std::string *cominfo = nullptr);
	uint64_t append_slt(RV64Oper op, RV64GFR src1, RV64GFR src2, RV64GFR dest);
	uint64_t append_slti(RV64Oper op, RV64GFR src1, int64_t imm12, RV64GFR dest);
	size_t append_load(RV64Opsz sz, RV64GFR base, RV64GFR dest, int64_t off12,
		std::string *cominfo = nullptr);
	size_t append_store(RV64Opsz sz, RV64GFR base, RV64GFR src2, int64_t off12,
		std::string *cominfo = nullptr);
	uint64_t append_ldaddr(RV64GFR dest, uint64_t xsymidx);
	uint64_t append_ldsymb(RV64Opsz sz, RV64GFR dest, uint64_t xsymidx);
	uint64_t append_ldimm(RV64GFR dest, int64_t imm64, std::string *cominfo = nullptr);
	uint64_t append_jump(uint64_t labelno);
	uint64_t append_call(uint64_t functidx);
	uint64_t append_cbranch(RV64Oper op, RV64GFR src1, RV64GFR src2, uint64_t lanelno);
	uint64_t append_ret(void);
	uint64_t append_move(RV64GFR src1, RV64GFR dest);
	size_t append_fload(RV64Opsz sz, RV64GFR base, RV64GFR fdest, int64_t off12,
		std::string *cominfo = nullptr);
	size_t append_fstore(RV64Opsz sz, RV64GFR base, RV64GFR fsrc2, int64_t off12,
		std::string *cominfo = nullptr);
	uint64_t append_farith(RV64Opsz sz, RV64Oper op, RV64GFR fsrc1, RV64GFR fsrc2,
		RV64GFR fdest, std::string *cominfo = nullptr);
	uint64_t append_fmove(RV64Opsz sz, RV64Oper op, RV64GFR fsrc1, RV64GFR fdest);
	uint64_t append_fmv2i(RV64Opsz sz, RV64GFR fsrc1, RV64GFR dest);
	uint64_t append_fmv4i(RV64Opsz sz, RV64GFR src1, RV64GFR fdest);
	uint64_t append_fcomp(RV64Opsz sz, RV64Oper op, RV64GFR fsrc1, RV64GFR fsrc2,
		RV64GFR dest);
	
	void exc_reg_not_allocated(HIRTempno t, RV64GFR r);
};

class HRV64Generator {
public:
	static RV64GFR GPR_order[unsigned(RV64GFR::NGPR)];
	static RV64GFR FPR_order[unsigned(RV64GFR::NGFR) - unsigned(RV64GFR::NGPR)];
	static RV64GFR aux_reg;
	static RV64Opsz integer_inst_size;
	static const char *RV64Asm_header;
	static const char *RV64Asm_ident;
private:
	// The index of an external symbol must be the same as that in `HIRCode`!
	std::vector<RV64XSymbol> xsyms_;
	std::vector<RV64Funct> funcs_;
	/*
	 * The number of builtin functions in IR.
	 */
	size_t nbuiltin_in_IR_;
public:
	void init_from_IR(const HIRCode &ircode);
	size_t search_func(const std::string &id) const;
	void generate(void);
	void print_inst(const RV64Inst& inst, size_t funcidx, std::ostream& os);
	void print_functions(std::ostream& os);
	void print_xvar(const RV64XSymbol& xvar, std::ostream& os);
	void print_data(std::ostream& os);
	void dump(std::ostream& os);
};

extern HRV64Generator hxd1_rv64gen;

#endif